/*
 * @Author: Clark
 * @Email: haixuanwoTxh@gmail.com
 * @Date: 2023-01-30 23:02:25
 * @LastEditors: Clark
 * @LastEditTime: 2023-01-30 23:35:51
 * @Description: file content
 */
#include "apue.h"
#include <pthread.h>
#include <limits.h>
#include <sys/time.h>

#define NTHR 8              // 线程数
#define NUMNUM 8000000L     // 数字数
#define TNUM (NUMNUM/NTHR)  // 每个线程的数字数

long nums[NUMNUM];
long snums[NUMNUM];

pthread_barrier_t b;

#define heapsort qsort
// #ifdef SOLARIS
// #define heapsort qsort
// #else
// extern int heapsort(void *, size_t, size_t, int (*)(const void*, const void*));
// #endif

// compare two long integers (helper function for heapsort)
int complong(const void *arg1, const void *arg2)
{
    long l1 = *(long *)arg1;
    long l2 = *(long *)arg2;

    if (l1 == l2)
    {
        return 0;
    }
    else if (l1 <l2)
    {
        return -1;
    }

    return 1;
}

// worker thread to sort a portion of the set of numbers
void *thr_fn(void *arg)
{
    long idx = (long)arg;

    heapsort(&nums[idx], TNUM, sizeof(long), complong);
    pthread_barrier_wait(&b);

    // go off and perform more work ...
    return ((void *)0);
}

// merge the results of the individual sorted rangs
void merge()
{
    long idx[NTHR];
    long minidx, num;

    for (long i = 0; i < NTHR; i++)
    {
        idx[i] = i * TNUM;
    }

    for (long sidx = 0; sidx < NUMNUM; sidx++)
    {
        num = LONG_MAX;
        for (long i = 0; i < NTHR; i++)
        {
            if ((idx[i] < (i+1)*TNUM) && (nums[idx[i]] < num))
            {
                num = nums[idx[i]];
                minidx = i;
            }
        }

        snums[sidx] = nums[idx[minidx]];
        idx[minidx]++;
    }
}

int main()
{
    unsigned long i;
    struct timeval start, end;
    long long startusec, endusec;
    double elapsed;
    int err;
    pthread_t tid;

    // create the initial set of number to sort
    srandom(1);
    for (unsigned long i = 0; i < NUMNUM; i++)
    {
        nums[i] = random();
    }

    // create 8 thread to sort the number
    gettimeofday(&start, NULL);
    pthread_barrier_init(&b, NULL, NTHR+1);

    for (unsigned long i = 0; i < NTHR; i++)
    {
        err = pthread_create(&tid, NULL, thr_fn, (void *)(i*TNUM));
        if (0 != err)
        {
            err_exit(err, "can't create thread");
        }
    }

    pthread_barrier_wait(&b);
    merge();
    gettimeofday(&end, NULL);

    // print the sorted list
    startusec = start.tv_sec * 1000000 + start.tv_usec;
    endusec   = end.tv_sec * 1000000 + end.tv_usec;
    elapsed = (double)(endusec - startusec)/1000000.0;
    printf("sort took %.4f seconds\n", elapsed);
    for (unsigned long i = 0; i < NUMNUM; i++)
    {
        printf("%ld\n", snums[i]);
    }

    exit(0);
}
